//
//  654_最大二叉树.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/9.
/*
 https://leetcode.cn/problems/maximum-binary-tree/description/
 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

 创建一个根节点，其值为 nums 中的最大值。
 递归地在最大值 左边 的 子数组前缀上 构建左子树。
 递归地在最大值 右边 的 子数组后缀上 构建右子树。
 返回 nums 构建的 最大二叉树 。
 */

import UIKit

class GetMaxBinaryTree: NSObject {
    /// 用栈实现左边、右边比它大的数
    private func parentArray(_ nums: [Int]) -> [Int] {
        if nums.count == 0 {
            return []
        }
        var leftParents = Array(repeating: -1, count: nums.count)
        var rightParents = Array(repeating: -1, count: nums.count)
        var stack = [Int]() // 依次递减栈
        for i in 0..<nums.count {
            while !stack.isEmpty, let top = stack.last, nums[i] > nums[top] {
                rightParents[top] = i
                stack.removeLast()
            }
            if let top = stack.last {
                leftParents[i] = top
            }
            stack.append(i)
        }
        
        var parents = [Int]()
        for index in 0..<leftParents.count {
            let left = leftParents[index]
            let right = rightParents[index]
            
            if left == -1 && right == -1 {
                parents.append(left)
                continue
            }
            if left == -1 {
                parents.append(right)
            } else if right == -1 {
                parents.append(left)
            } else if nums[left] <  nums[right]{
                parents.append(left)
            } else {
                parents.append(right)
            }
        }
        return parents
    }
    /// 用递归实现
    func constructMaximumBinaryTree(_ nums: [Int]) -> TreeNode<Int>? {
        return fenGeArray(nums, 0, nums.count)
    }

    /// 递归方法
    /// - Parameters:
    ///   - nums: 数组
    ///   - l: 【l， r)
    ///   - r: [l， r)
    private func fenGeArray(_ nums: [Int], _ l: Int, _ r: Int) -> TreeNode<Int>? {
        if r == l {
            return nil
        }
        var maxIndex = l
        for index in l..<r {
            if nums[index] > nums[maxIndex] {
                maxIndex = index
            }
        }
        let root = TreeNode(nums[maxIndex])
        let leftNode = fenGeArray(nums, l, maxIndex)
        let rightNode = fenGeArray(nums, maxIndex + 1, r)
        root.left = leftNode
        root.right = rightNode
        return root
    }
}
